﻿#define _CRT_SECURE_NO_WARNINGS

//
//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, q, a[N];
//
//int main()
//{
//    cin >> n >> q;
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    while (q--)
//    {
//        int x;
//        cin >> x;
//        int l = 0, r = n - 1;
//        while (l < r)
//        {
//            int mid = (l + r) >> 1;
//            if (a[mid] >= x) r = mid;
//            else l = mid + 1;
//        }
//        if (a[l] != x) cout << "-1 -1" << endl;
//        else
//        {
//            cout << l << ' ';
//            l = 0, r = n - 1;
//            while (l < r)
//            {
//                int mid = (l + r + 1) >> 1;
//                if (a[mid] <= x) l = mid;
//                else r = mid - 1;
//            }
//            cout << l << endl;
//        }
//    }
//
//    return 0;
//}

//
//#include <iostream>
//#include <vector>
//using namespace std;
//
//vector<int> add(vector<int>& A, vector<int>& B)
//{
//    vector<int> C;
//
//    int tmp = 0;
//    for (int i = 0; i < A.size() || i < B.size() || tmp; i++)
//    {
//        if (i < A.size()) tmp += A[i];
//        if (i < B.size()) tmp += B[i];
//        C.push_back(tmp % 10);
//        tmp /= 10;
//    }
//
//    return C;
//}
//
//int main()
//{
//    vector<int> A, B;
//    string a, b;
//    cin >> a >> b;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
//
//    auto C = add(A, B);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    cout << endl;
//
//    return 0;
//}


//#include <iostream>
//using namespace std;
//
//void test() { int a = 10, return a; }
//
//int main()
//{
//	test();
//
//	return 0;
//}


//namespace my_list
//{
//	template<class T>
//	struct __list_node
//	{
//		__list_node* _prev;
//		__list_node* _next;
//		T _data;
//
//		__list_node(const T& x) :_prev(nullptr), _next(nullptr), _data(x) {}
//	};
//
//	template<class T, class Ref, class Ptr>
//	struct __list_iterator
//	{
//		typedef __list_node<T> node;
//		typedef __list_iterator<T, Ref, Ptr> Self;
//		node* _pnode;
//
//		__list_iterator(node* p) : _pnode(p) {}
//
//		Ref operator*() { return _pnode->_data; }
//		Ptr operator->() { return &_pnode->_data; }
//
//		Self& operator++() { _pnode = _pnode->_next; return *this; }
//		Self operator++(int)
//		{
//			Self tmp(*this);
//			_pnode = _pnode->_next;
//			return tmp;
//		}
//		Self& operator--() { _pnode = _pnode->_prev; return *this; }
//		Self operator--(int)
//		{
//			Self tmp(*this);
//			_pnode = _pnode->_prev;
//			return tmp;
//		}
//
//		Self operator+(size_t num)
//		{
//			Self tmp(*this);
//			while (num--) tmp._pnode = tmp._pnode->_next;
//			return tmp;
//		}
//		Self operator-(size_t num)
//		{
//			Self tmp(*this);
//			while (num--) tmp._pnode = tmp._pnode->_prev;
//			return tmp;
//		}
//
//		Self& operator=(const Self& it) { _pnode = it._pnode; return *this; }
//
//		bool operator==(const Self& it) { return _pnode == it._pnode; }
//		bool operator!=(const Self& it) { return _pnode != it._pnode; }
//	};
//
//	template<typename T>
//	class list
//	{
//		typedef __list_node<T> node;
//	public:
//		typedef __list_iterator<T, T&, T*> iterator;
//		typedef __list_iterator<T, const T&, const T*> const_iterator;
//
//		void empty_initialize()
//		{
//			_head = new node(T());
//			_head->_next = _head;
//			_head->_prev = _head;
//			_size = 0;
//		}
//
//		iterator begin() { return iterator(_head->_next); }
//		iterator end() { return iterator(_head); }
//		const_iterator begin() const { return const_iterator(_head->_next); }
//		const_iterator end() const { return const_iterator(_head); }
//
//		list() { empty_initialize(); }
//
//		// ͳд
//		//list(const list<T>& l) { empty_initialize(); for (const auto& e : l) push_back(e); }
//
//		// ִд
//		template<class InputIterator>
//		list(InputIterator first, InputIterator last)
//		{
//			empty_initialize();
//			while (first != last)
//			{
//				push_back(*first);
//				++first;
//			}
//		}
//
//		list(const list<T>& l)
//		{
//			empty_initialize();
//			list<T> tmp(l.begin(), l.end());
//			swap(tmp);
//		}
//
//		list<T>& operator=(list<T> l) { swap(l); return *this; }
//
//		~list()
//		{
//			clear();
//			delete _head;
//			_head = nullptr;
//		}
//
//		void swap(list<T>& l)
//		{
//			std::swap(_head, l._head);
//			std::swap(_size, l._size);
//		}
//
//		void clear()
//		{
//			iterator it = begin();
//			while (it != end()) it = erase(it);
//		}
//
//		void push_back(const T& x)
//		{
//			//node* newnode = new node(x);
//			//node* cur = _head->_prev;
//			//cur->_next = newnode;
//			//newnode->_prev = cur;
//			//_head->_prev = newnode;
//			//newnode->_next = _head;
//
//			insert(end(), x);
//		}
//		void pop_back()
//		{
//			//assert(!empty());
//
//			//node* tmp = _head->_prev;
//			//node* cur = tmp->_prev;
//			//delete tmp;
//			//cur->_next = _head;
//			//_head->_prev = cur;
//
//			erase(--end());
//		}
//		void push_front(const T& x)
//		{
//			//node* newnode = new node(x);
//			//node* next = _head->_next;
//			//newnode->_next = next;
//			//next->_prev = newnode;
//			//_head->_next = newnode;
//			//newnode->_prev = _head;
//
//			insert(begin(), x);
//		}
//		void pop_front()
//		{
//			//assert(!empty());
//
//			//node* tmp = _head->_next;
//			//node* cur = _head->_next->_next;
//			//delete tmp;
//			//_head->_next = cur;
//			//cur->_prev = _head;
//
//			erase(begin());
//		}
//
//		iterator insert(iterator pos, const T& x)
//		{
//			node* newnode = new node(x);
//			node* cur = pos._pnode;
//			node* prev = cur->_prev;
//			prev->_next = newnode;
//			newnode->_prev = prev;
//			newnode->_next = cur;
//			cur->_prev = newnode;
//			_size++;
//
//			return iterator(newnode);
//		}
//
//		iterator erase(iterator pos)
//		{
//			assert(!empty() && pos._pnode != _head);
//
//			node* cur = pos._pnode;
//			node* prev = cur->_prev;
//			node* next = cur->_next;
//			delete cur;
//			prev->_next = next;
//			next->_prev = prev;
//
//			return iterator(next);
//		}
//
//		bool empty() { return _size == 0; }
//
//		void print() const
//		{
//			for (const auto& e : *this)
//				cout << e << ' ';
//			cout << endl;
//		}
//		void print()
//		{
//			for (auto& e : *this)
//				cout << e << ' ';
//			cout << endl;
//		}
//
//	private:
//		node* _head;
//		size_t _size;
//	};
//
//	void test1()
//	{
//		list<int> l1;
//		l1.push_back(1);
//		l1.push_back(2);
//		l1.push_back(3);
//		l1.push_back(4);
//		l1.push_back(5);
//		l1.print();
//
//		list<int> l2 = l1;
//		l2.print();
//
//		list<int> l3 = l1;
//		l3.push_front(999);
//		l3.push_front(999);
//		l3.push_front(999);
//		l3.push_front(999);
//		l3.push_front(999);
//		l3.print();
//
//		l2 = l3;
//		l2.print();
//
//		l2.pop_back();
//		l2.pop_back();
//		l2.pop_back();
//		l2.print();
//
//		l2.pop_front();
//		l2.pop_front();
//		l2.pop_front();
//		l2.print();
//
//		l2.insert(l2.begin()++, 1000);
//		l2.print();
//
//		list<int>::iterator it = l2.begin();
//		it = ++(l2.insert(it, 2222));
//		l2.print();
//		cout << *it << endl;
//
//		l3.pop_back();
//		l3.pop_back();
//		l3.pop_back();
//		l3.pop_back();
//		l3.pop_back();
//		l3.print();
//
//		l3.insert(l3.begin() + 2, 888);
//		l3.print();
//
//		l3.erase(l3.begin() - 2);
//		l3.print();
//	}
//}

#include <iostream>
#include <assert.h>
#include <list>
using namespace std;

namespace my_list
{
	template<class T>
	struct __list_node
	{
		__list_node* _prev;
		__list_node* _next;
		T _data;

		__list_node(const T& x) :_prev(nullptr), _next(nullptr), _data(x) {}
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T> node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		node* _pnode;

		__list_iterator(node* p) : _pnode(p) {}

		Ref operator*() { return _pnode->_data; }
		Ptr operator->() { return &_pnode->_data; }

		Self& operator++() { _pnode = _pnode->_next; return *this; }
		Self operator++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		Self& operator--() { _pnode = _pnode->_prev; return *this; }
		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		Self operator+(size_t num)
		{
			Self tmp(*this);
			while (num--) tmp._pnode = tmp._pnode->_next;
			return tmp;
		}
		Self operator-(size_t num)
		{
			Self tmp(*this);
			while (num--) tmp._pnode = tmp._pnode->_prev;
			return tmp;
		}

		Self& operator=(const Self& it) { _pnode = it._pnode; return *this; }

		bool operator==(const Self& it) { return _pnode == it._pnode; }
		bool operator!=(const Self& it) { return _pnode != it._pnode; }
	};

	template<typename T>
	class list
	{
		typedef __list_node<T> node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		void empty_initialize()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		iterator begin() { return iterator(_head->_next); }
		iterator end() { return iterator(_head); }
		const_iterator begin() const { return const_iterator(_head->_next); }
		const_iterator end() const { return const_iterator(_head); }

		list() { empty_initialize(); }

		// ͳд
		//list(const list<T>& l) { empty_initialize(); for (const auto& e : l) push_back(e); }

		// ִд
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			empty_initialize();
			list<T> tmp(l.begin(), l.end());
			swap(tmp);
		}

		list<T>& operator=(list<T> l) { swap(l); return *this; }

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void swap(list<T>& l)
		{
			std::swap(_head, l._head);
			std::swap(_size, l._size);
		}

		void clear()
		{
			iterator it = begin();
			while (it != end()) it = erase(it);
		}

		void push_back(const T& x)
		{
			//node* newnode = new node(x);
			//node* cur = _head->_prev;
			//cur->_next = newnode;
			//newnode->_prev = cur;
			//_head->_prev = newnode;
			//newnode->_next = _head;

			insert(end(), x);
		}
		void pop_back()
		{
			//assert(!empty());

			//node* tmp = _head->_prev;
			//node* cur = tmp->_prev;
			//delete tmp;
			//cur->_next = _head;
			//_head->_prev = cur;

			erase(--end());
		}
		void push_front(const T& x)
		{
			//node* newnode = new node(x);
			//node* next = _head->_next;
			//newnode->_next = next;
			//next->_prev = newnode;
			//_head->_next = newnode;
			//newnode->_prev = _head;

			insert(begin(), x);
		}
		void pop_front()
		{
			//assert(!empty());

			//node* tmp = _head->_next;
			//node* cur = _head->_next->_next;
			//delete tmp;
			//_head->_next = cur;
			//cur->_prev = _head;

			erase(begin());
		}

		iterator insert(iterator pos, const T& x)
		{
			node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			assert(!empty() && pos._pnode != _head);

			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;

			return iterator(next);
		}

		bool empty() { return _size == 0; }

		void print() const
		{
			for (const auto& e : *this)
				cout << e << ' ';
			cout << endl;
		}
		void print()
		{
			for (auto& e : *this)
				cout << e << ' ';
			cout << endl;
		}

	private:
		node* _head;
		size_t _size;
	};

	void test1()
	{
		list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		l1.push_back(3);
		l1.push_back(4);
		l1.push_back(5);
		l1.print();

		list<int> l2 = l1;
		l2.print();

		list<int> l3 = l1;
		l3.push_front(999);
		l3.push_front(999);
		l3.push_front(999);
		l3.push_front(999);
		l3.push_front(999);
		l3.print();

		l2 = l3;
		l2.print();

		l2.pop_back();
		l2.pop_back();
		l2.pop_back();
		l2.print();

		l2.pop_front();
		l2.pop_front();
		l2.pop_front();
		l2.print();

		l2.insert(l2.begin()++, 1000);
		l2.print();

		list<int>::iterator it = l2.begin();
		it = ++(l2.insert(it, 2222));
		l2.print();
		/*cout << *it << endl;*/

		l3.pop_back();
		l3.pop_back();
		l3.pop_back();
		l3.pop_back();
		l3.pop_back();
		l3.print();

		l3.insert(l3.begin() + 2, 888);
		l3.print();

		l3.erase(l3.begin() - 2);
		l3.print();
	}
}

